#pragma once

#include  "iostream"
#include  "vector"
#include  "stack"
#include  "unordered_map"
#include   "queue"

using namespace std;

/*
 * https://leetcode.cn/problems/count-of-smaller-numbers-after-self/description/
 * 315. 计算右侧小于当前元素的个数
困难
965
相关企业
给你一个整数数组 nums ，按要求返回一个新数组 counts 。数组 counts 有该性质： counts[i] 的值是  nums[i] 右侧小于 nums[i] 的元素的数量。



示例 1：

输入：nums = [5,2,6,1]
输出：[2,1,1,0]
解释：
5 的右侧有 2 个更小的元素 (2 和 1)
2 的右侧仅有 1 个更小的元素 (1)
6 的右侧有 1 个更小的元素 (1)
1 的右侧有 0 个更小的元素
示例 2：

输入：nums = [-1]
输出：[0]
示例 3：

输入：nums = [-1,-1]
输出：[0,0]
 *
 *
 * TODO 这个必须保存下标的 因为res[i]+=(数值) 这个个数并不是一次就算出来的 如果直接是一个总数直接加倒没问题
 *  但是这种必须加所以咱们直接索引排序 .nums 不变
 * */

vector<int> res;

void merge(vector<std::pair<int, int> > &nums, int low, int high, int mid) {
    //还是区间这里出错 了 需要多加练习
    vector<std::pair<int, int>> left(nums.begin() + low,
                                     nums.begin() + mid + 1);//区间内另一个数组的元素到vector中,注意最后面的end其实并不包括 其实后面就是一个长度
    vector<std::pair<int, int> > right(nums.begin() + mid + 1, nums.begin() + 1 + high);
    int i = 0, j = 0;
    int index = low;
    while (i < left.size() && j < right.size()) {
        //这个题还有一个坑 我没写等号 ...擦写了也不对
        if (left[i].first > right[j].first) {
            //count+=i;//获取j前面元素个数


            res[left[i].second] += (high - mid - j);//主要是这个 改了好长时间没里过来 唉日了!!!!!!!
            nums[index++] = left[i++];

        } else {
            ///5 7    4  6
            //当左边数组的大与右边数组的元素时，就对当前元素以及后面的元素的个数进行统计，
            //mid -low +1算出区间长度 -i 例如 57 46 如果4<5 则一定有 4<5 后面的数 因此只要求 left.size()-i当前位置


            // 如果是递减 的话  8 5  7 3==> 如果7>5 则 7 肯定大于5后面的数 但是这种似乎不对
            // 8>7 则8肯定大于7后面的数


            //for(int k=i;k<left.size();k++)
            // {
            // res[left[i].second]+=1;
            //}

            //res[nums[j].second]+=(mid-low-i+1);
            nums[index++] = right[j++];


        }

    }

    while (i < left.size()) {

        nums[index++] = left[i++];
    }
    while (j < right.size()) {
        nums[index++] = right[j++];
    }

}

void merge_sort(vector<std::pair<int, int>> &nums, int low, int high) {

    if (low < high) {
        int mid = low + (high - low) / 2;
        merge_sort(nums, low, mid);
        merge_sort(nums, mid + 1, high);
        merge(nums, low, high, mid);

    }


}

vector<int> countSmaller(vector<int> &nums) {

    vector<std::pair<int, int>> nums_;
    for (int i = 0; i < nums.size(); ++i) {
        nums_.emplace_back(nums[i], i);
    }

    res.resize(nums.size(), 0);


    merge_sort(nums_, 0, nums_.size() - 1);
    return res;
}